<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8" />
  <title>Real Use Cases &raquo; Static Timing Analysis | Taskflow QuickStart</title>
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,400i,600,600i%7CSource+Code+Pro:400,400i,600" />
  <link rel="stylesheet" href="m-dark+documentation.compiled.css" />
  <link rel="icon" href="favicon.ico" type="image/x-icon" />
  <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  <meta name="theme-color" content="#22272e" />
</head>
<body>
<header><nav id="navigation">
  <div class="m-container">
    <div class="m-row">
      <span id="m-navbar-brand" class="m-col-t-8 m-col-m-none m-left-m">
        <a href="https://taskflow.github.io"><img src="taskflow_logo.png" alt="" />Taskflow</a> <span class="m-breadcrumb">|</span> <a href="index.html" class="m-thin">QuickStart</a>
      </span>
      <div class="m-col-t-4 m-hide-m m-text-right m-nopadr">
        <a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
          <path id="m-doc-search-icon-path" d="m6 0c-3.31 0-6 2.69-6 6 0 3.31 2.69 6 6 6 1.49 0 2.85-0.541 3.89-1.44-0.0164 0.338 0.147 0.759 0.5 1.15l3.22 3.79c0.552 0.614 1.45 0.665 2 0.115 0.55-0.55 0.499-1.45-0.115-2l-3.79-3.22c-0.392-0.353-0.812-0.515-1.15-0.5 0.895-1.05 1.44-2.41 1.44-3.89 0-3.31-2.69-6-6-6zm0 1.56a4.44 4.44 0 0 1 4.44 4.44 4.44 4.44 0 0 1-4.44 4.44 4.44 4.44 0 0 1-4.44-4.44 4.44 4.44 0 0 1 4.44-4.44z"/>
        </svg></a>
        <a id="m-navbar-show" href="#navigation" title="Show navigation"></a>
        <a id="m-navbar-hide" href="#" title="Hide navigation"></a>
      </div>
      <div id="m-navbar-collapse" class="m-col-t-12 m-show-m m-col-m-none m-right-m">
        <div class="m-row">
          <ol class="m-col-t-6 m-col-m-none">
            <li><a href="pages.html">Handbook</a></li>
            <li><a href="namespaces.html">Namespaces</a></li>
          </ol>
          <ol class="m-col-t-6 m-col-m-none" start="3">
            <li><a href="annotated.html">Classes</a></li>
            <li><a href="files.html">Files</a></li>
            <li class="m-show-m"><a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
              <use href="#m-doc-search-icon-path" />
            </svg></a></li>
          </ol>
        </div>
      </div>
    </div>
  </div>
</nav></header>
<main><article>
  <div class="m-container m-container-inflatable">
    <div class="m-row">
      <div class="m-col-l-10 m-push-l-1">
        <h1>
          <span class="m-breadcrumb"><a href="usecases.html">Real Use Cases</a> &raquo;</span>
          Static Timing Analysis
        </h1>
        <nav class="m-block m-default">
          <h3>Contents</h3>
          <ul>
            <li><a href="#UseCasesOpenTimer">OpenTimer: A High-performance Timing Analysis Tool</a></li>
            <li><a href="#UseCaseOpenTimerProgrammingEffort">Programming Effort</a></li>
            <li><a href="#UseCaseOpenTimerPerformanceImprovement">Performance Improvement</a></li>
            <li><a href="#UseCaseOpenTimerConclusion">Conclusion</a></li>
            <li><a href="#UseCaseOpenTimerReferences">References</a></li>
          </ul>
        </nav>
<p>We have applied Taskflow to solve a real-world VLSI static timing analysis problem that incorporates hundreds of millions of tasks and dependencies. The goal is to analyze the timing behavior of a design.</p><section id="UseCasesOpenTimer"><h2><a href="#UseCasesOpenTimer">OpenTimer: A High-performance Timing Analysis Tool</a></h2><p>Static timing analysis (STA) is an important step in the overall chip design flow. It verifies the static behavior of a circuit design and ensure its correct functionality under the given clock speed. However, efficient parallel timing analysis is extremely challenging to design and implement, due to large irregularity and graph-oriented computing. The following figure shows an extracted timing graph from an industrial design.</p><img class="m-image" src="opentimer_1.png" alt="Image" /><p>We consider our research project <a href="https://github.com/OpenTimer/OpenTimer">OpenTimer</a>, an open-source static timing analyzer that has been used in many industrial and academic projects. The first release v1 in 2015 implemented the <em>pipeline-based levelization</em> algorithm using the OpenMP 4.5 task dependency clause. To overcome the performance bottleneck caused by pipeline, we rewrote the core incremental timing engine using Taskflow in the second release v2.</p></section><section id="UseCaseOpenTimerProgrammingEffort"><h2><a href="#UseCaseOpenTimerProgrammingEffort">Programming Effort</a></h2><p>The table below measures the software costs of two OpenTimer versions using the Linux tool <a href="https://dwheeler.com/sloccount/">SLOCCount</a>. In OpenTimer v2, a large amount of exhaustive OpenMP dependency clauses that were used to carry out task dependencies are now replaced with only a few lines of flexible Taskflow code (9123 vs 4482). The maximum cyclomatic complexity in a single function is reduced from 58 to 20, due to Taskflow&#x27;s programmability.</p><table class="m-table"><thead><tr><th>Tool</th><th>Task Model</th><th>Lines of Code</th><th>Cyclomatic Complexity</th><th>Cost</th></tr></thead><tbody><tr><td>OpenTimer v1</td><td>OpenMP 4.5</td><td>9123</td><td>58</td><td>$275,287</td></tr><tr><td>OpenTimer v2</td><td>Taskflow</td><td>4482</td><td>20</td><td>$130,523</td></tr></tbody></table><p>OpenTimer v1 relied on a pipeline data structure to adtop loop parallelism with OpenMP. We found it very difficult to go beyond this paradigm because of the insufficient support for dynamic dependencies in OpenMP. With Taskflow in place, we can break this bottleneck and easily model both static and dynamic task dependencies at programming time and runtime. The task dependency graph flows computations naturally with the timing graph, providing improved asynchrony and performance. The following figure shows a task graph to carry one iteration of timing update.</p><div class="m-graph"><svg style="width: 52.100rem; height: 112.400rem;" viewBox="0.00 0.00 521.24 1124.00">
<g transform="scale(1 1) rotate(0) translate(4 1120)">
<title>Taskflow</title>
<g class="m-node">
<title>[A33] bprop_tau2015_clk</title>
<ellipse cx="150.96" cy="-18" rx="73.37" ry="18"/>
<text text-anchor="middle" x="150.96" y="-14.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A33] bprop_tau2015_clk</text>
</g>
<g class="m-node">
<title>[A32] bprop_f1:CLK</title>
<ellipse cx="150.96" cy="-90" rx="60.5" ry="18"/>
<text text-anchor="middle" x="150.96" y="-86.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A32] bprop_f1:CLK</text>
</g>
<g class="m-edge">
<title>[A32] bprop_f1:CLK&#45;&gt;[A33] bprop_tau2015_clk</title>
<path d="M150.96,-71.7C150.96,-64.41 150.96,-55.73 150.96,-47.54"/>
<polygon points="154.46,-47.62 150.96,-37.62 147.46,-47.62 154.46,-47.62"/>
</g>
<g class="m-node">
<title>[A31] bprop_f1:Q</title>
<ellipse cx="204.96" cy="-162" rx="53.4" ry="18"/>
<text text-anchor="middle" x="204.96" y="-158.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A31] bprop_f1:Q</text>
</g>
<g class="m-edge">
<title>[A31] bprop_f1:Q&#45;&gt;[A32] bprop_f1:CLK</title>
<path d="M186.63,-144.76C179.43,-136.61 171.4,-126.53 164.69,-117.31"/>
<polygon points="167.73,-115.55 159.14,-109.36 162,-119.57 167.73,-115.55"/>
</g>
<g class="m-edge">
<title>[A31] bprop_f1:Q&#45;&gt;[A32] bprop_f1:CLK</title>
<path d="M197.52,-143.7C191.92,-135.32 184.23,-125.1 176.66,-115.9"/>
<polygon points="179.33,-113.64 170.18,-108.3 174,-118.18 179.33,-113.64"/>
</g>
<g class="m-node">
<title>[A30] bprop_u4:B</title>
<ellipse cx="204.96" cy="-234" rx="54.29" ry="18"/>
<text text-anchor="middle" x="204.96" y="-230.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A30] bprop_u4:B</text>
</g>
<g class="m-edge">
<title>[A30] bprop_u4:B&#45;&gt;[A31] bprop_f1:Q</title>
<path d="M204.96,-215.7C204.96,-208.41 204.96,-199.73 204.96,-191.54"/>
<polygon points="208.46,-191.62 204.96,-181.62 201.46,-191.62 208.46,-191.62"/>
</g>
<g class="m-node">
<title>[A29] bprop_u2:A</title>
<ellipse cx="458.96" cy="-234" rx="54.29" ry="18"/>
<text text-anchor="middle" x="458.96" y="-230.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A29] bprop_u2:A</text>
</g>
<g class="m-edge">
<title>[A29] bprop_u2:A&#45;&gt;[A31] bprop_f1:Q</title>
<path d="M418.15,-221.75C374.14,-209.62 303.98,-190.29 256.26,-177.14"/>
<polygon points="257.28,-173.79 246.7,-174.51 255.42,-180.54 257.28,-173.79"/>
</g>
<g class="m-node">
<title>[A28] bprop_u2:Y</title>
<ellipse cx="458.96" cy="-306" rx="54.29" ry="18"/>
<text text-anchor="middle" x="458.96" y="-302.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A28] bprop_u2:Y</text>
</g>
<g class="m-edge">
<title>[A28] bprop_u2:Y&#45;&gt;[A29] bprop_u2:A</title>
<path d="M453.04,-287.7C452.29,-280.41 452.05,-271.73 452.31,-263.54"/>
<polygon points="455.8,-263.82 452.96,-253.61 448.81,-263.36 455.8,-263.82"/>
</g>
<g class="m-edge">
<title>[A28] bprop_u2:Y&#45;&gt;[A29] bprop_u2:A</title>
<path d="M464.87,-287.7C465.62,-280.41 465.87,-271.73 465.6,-263.54"/>
<polygon points="469.1,-263.36 464.95,-253.61 462.11,-263.82 469.1,-263.36"/>
</g>
<g class="m-node">
<title>[A27] bprop_u3:A</title>
<ellipse cx="453.96" cy="-378" rx="54.29" ry="18"/>
<text text-anchor="middle" x="453.96" y="-374.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A27] bprop_u3:A</text>
</g>
<g class="m-edge">
<title>[A27] bprop_u3:A&#45;&gt;[A28] bprop_u2:Y</title>
<path d="M455.19,-359.7C455.71,-352.41 456.33,-343.73 456.92,-335.54"/>
<polygon points="460.41,-335.84 457.63,-325.61 453.42,-335.34 460.41,-335.84"/>
</g>
<g class="m-node">
<title>[A26] bprop_u3:Y</title>
<ellipse cx="453.96" cy="-450" rx="54.29" ry="18"/>
<text text-anchor="middle" x="453.96" y="-446.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A26] bprop_u3:Y</text>
</g>
<g class="m-edge">
<title>[A26] bprop_u3:Y&#45;&gt;[A27] bprop_u3:A</title>
<path d="M448.04,-431.7C447.29,-424.41 447.05,-415.73 447.31,-407.54"/>
<polygon points="450.8,-407.82 447.96,-397.61 443.81,-407.36 450.8,-407.82"/>
</g>
<g class="m-edge">
<title>[A26] bprop_u3:Y&#45;&gt;[A27] bprop_u3:A</title>
<path d="M459.87,-431.7C460.62,-424.41 460.87,-415.73 460.6,-407.54"/>
<polygon points="464.1,-407.36 459.95,-397.61 457.11,-407.82 464.1,-407.36"/>
</g>
<g class="m-node">
<title>[A25] bprop_out</title>
<ellipse cx="443.96" cy="-522" rx="50.29" ry="18"/>
<text text-anchor="middle" x="443.96" y="-518.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A25] bprop_out</text>
</g>
<g class="m-edge">
<title>[A25] bprop_out&#45;&gt;[A26] bprop_u3:Y</title>
<path d="M446.43,-503.7C447.48,-496.32 448.74,-487.52 449.92,-479.25"/>
<polygon points="453.35,-480 451.3,-469.6 446.42,-479.01 453.35,-480"/>
</g>
<g class="m-node">
<title>[A24] bprop_inp2</title>
<ellipse cx="312.96" cy="-18" rx="52.96" ry="18"/>
<text text-anchor="middle" x="312.96" y="-14.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A24] bprop_inp2</text>
</g>
<g class="m-node">
<title>[A23] bprop_u1:B</title>
<ellipse cx="312.96" cy="-90" rx="54.29" ry="18"/>
<text text-anchor="middle" x="312.96" y="-86.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A23] bprop_u1:B</text>
</g>
<g class="m-edge">
<title>[A23] bprop_u1:B&#45;&gt;[A24] bprop_inp2</title>
<path d="M312.96,-71.7C312.96,-64.41 312.96,-55.73 312.96,-47.54"/>
<polygon points="316.46,-47.62 312.96,-37.62 309.46,-47.62 316.46,-47.62"/>
</g>
<g class="m-node">
<title>[A22] bprop_inp1</title>
<ellipse cx="439.96" cy="-18" rx="52.96" ry="18"/>
<text text-anchor="middle" x="439.96" y="-14.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A22] bprop_inp1</text>
</g>
<g class="m-node">
<title>[A21] bprop_u1:A</title>
<ellipse cx="439.96" cy="-90" rx="54.29" ry="18"/>
<text text-anchor="middle" x="439.96" y="-86.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A21] bprop_u1:A</text>
</g>
<g class="m-edge">
<title>[A21] bprop_u1:A&#45;&gt;[A22] bprop_inp1</title>
<path d="M439.96,-71.7C439.96,-64.41 439.96,-55.73 439.96,-47.54"/>
<polygon points="443.46,-47.62 439.96,-37.62 436.46,-47.62 443.46,-47.62"/>
</g>
<g class="m-node">
<title>[A20] bprop_u1:Y</title>
<ellipse cx="331.96" cy="-162" rx="54.29" ry="18"/>
<text text-anchor="middle" x="331.96" y="-158.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A20] bprop_u1:Y</text>
</g>
<g class="m-edge">
<title>[A20] bprop_u1:Y&#45;&gt;[A23] bprop_u1:B</title>
<path d="M321.48,-144.05C318.7,-136.68 316.04,-127.84 314.05,-119.51"/>
<polygon points="317.49,-118.84 312.04,-109.76 310.63,-120.26 317.49,-118.84"/>
</g>
<g class="m-edge">
<title>[A20] bprop_u1:Y&#45;&gt;[A23] bprop_u1:B</title>
<path d="M333.18,-143.7C331.92,-136.24 329.74,-127.32 327.17,-118.97"/>
<polygon points="330.5,-117.89 323.98,-109.54 323.87,-120.13 330.5,-117.89"/>
</g>
<g class="m-edge">
<title>[A20] bprop_u1:Y&#45;&gt;[A21] bprop_u1:A</title>
<path d="M351.2,-144.76C365.31,-134.91 384.73,-122.23 401.86,-111.66"/>
<polygon points="403.61,-114.69 410.34,-106.5 399.98,-108.71 403.61,-114.69"/>
</g>
<g class="m-edge">
<title>[A20] bprop_u1:Y&#45;&gt;[A21] bprop_u1:A</title>
<path d="M360.21,-146.33C376.07,-136.83 395.67,-124.28 411.54,-113.54"/>
<polygon points="413.37,-116.53 419.63,-107.98 409.4,-110.76 413.37,-116.53"/>
</g>
<g class="m-node">
<title>[A19] bprop_u4:A</title>
<ellipse cx="331.96" cy="-234" rx="54.29" ry="18"/>
<text text-anchor="middle" x="331.96" y="-230.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A19] bprop_u4:A</text>
</g>
<g class="m-edge">
<title>[A19] bprop_u4:A&#45;&gt;[A20] bprop_u1:Y</title>
<path d="M331.96,-215.7C331.96,-208.41 331.96,-199.73 331.96,-191.54"/>
<polygon points="335.46,-191.62 331.96,-181.62 328.46,-191.62 335.46,-191.62"/>
</g>
<g class="m-node">
<title>[A18] bprop_u4:Y</title>
<ellipse cx="204.96" cy="-306" rx="54.29" ry="18"/>
<text text-anchor="middle" x="204.96" y="-302.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A18] bprop_u4:Y</text>
</g>
<g class="m-edge">
<title>[A18] bprop_u4:Y&#45;&gt;[A30] bprop_u4:B</title>
<path d="M199.04,-287.7C198.29,-280.41 198.05,-271.73 198.31,-263.54"/>
<polygon points="201.8,-263.82 198.96,-253.61 194.81,-263.36 201.8,-263.82"/>
</g>
<g class="m-edge">
<title>[A18] bprop_u4:Y&#45;&gt;[A30] bprop_u4:B</title>
<path d="M210.87,-287.7C211.62,-280.41 211.87,-271.73 211.6,-263.54"/>
<polygon points="215.1,-263.36 210.95,-253.61 208.11,-263.82 215.1,-263.36"/>
</g>
<g class="m-edge">
<title>[A18] bprop_u4:Y&#45;&gt;[A19] bprop_u4:A</title>
<path d="M227.72,-289.29C245.36,-278.9 270.08,-265.21 291.08,-254.17"/>
<polygon points="292.44,-257.41 299.69,-249.69 289.21,-251.2 292.44,-257.41"/>
</g>
<g class="m-edge">
<title>[A18] bprop_u4:Y&#45;&gt;[A19] bprop_u4:A</title>
<path d="M236.21,-290.83C255.45,-280.95 279.96,-267.57 299.43,-256.39"/>
<polygon points="301.18,-259.42 308.06,-251.37 297.66,-253.37 301.18,-259.42"/>
</g>
<g class="m-node">
<title>[A17] bprop_f1:D</title>
<ellipse cx="134.96" cy="-378" rx="53.4" ry="18"/>
<text text-anchor="middle" x="134.96" y="-374.12" font-family="Helvetica,sans-Serif" font-size="10.00" fill="white">[A17] bprop_f1:D</text>
</g>
<g class="m-edge">
<title>[A17] bprop_f1:D&#45;&gt;[A32] bprop_f1:CLK</title>
<path d="M130.13,-359.71C125.82,-320.99 126.53,-224.41 133.96,-144 134.7,-135.91 135.87,-127.17 137.45,-119.16"/>
<polygon points="140.81,-120.13 139.69,-109.6 134,-118.53 140.81,-120.13"/>
</g>
<g class="m-edge">
<title>[A17] bprop_f1:D&#45;&gt;[A32] bprop_f1:CLK</title>
<path d="M139.61,-359.71C143.82,-320.99 144.53,-224.41 151.96,-144 152.7,-136 153.85,-127.37 154.7,-119.44"/>
<polygon points="158.17,-119.9 155.55,-109.63 151.2,-119.29 158.17,-119.9"/>
</g>
<g class="m-edge">
<title>[A17] bprop_f1:D&#45;&gt;[A18] bprop_u4:Y</title>
<path d="M151.55,-360.41C160.18,-351.78 170.89,-341.06 180.46,-331.5"/>
<polygon points="182.82,-334.09 187.42,-324.54 177.87,-329.14 182.82,-334.09"/>
</g>
<g class="m-node m-flat">
<title>[A16] fprop_f1:D</title>
<ellipse cx="260.96" cy="-738" rx="52.07" ry="18"/>
<text text-anchor="middle" x="260.96" y="-734.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A16] fprop_f1:D</text>
</g>
<g class="m-edge">
<title>[A16] fprop_f1:D&#45;&gt;[A17] bprop_f1:D</title>
<path d="M243.55,-720.93C218.95,-696.36 176.96,-646.84 176.96,-595 176.96,-595 176.96,-595 176.96,-521 176.96,-479.69 160.41,-434.3 148.09,-406.22"/>
<polygon points="151.4,-405.05 144.08,-397.39 145.03,-407.94 151.4,-405.05"/>
</g>
<g class="m-node m-flat">
<title>[A15] fprop_u4:Y</title>
<ellipse cx="232.96" cy="-810" rx="52.96" ry="18"/>
<text text-anchor="middle" x="232.96" y="-806.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A15] fprop_u4:Y</text>
</g>
<g class="m-edge">
<title>[A15] fprop_u4:Y&#45;&gt;[A16] fprop_f1:D</title>
<path d="M239.88,-791.7C242.9,-784.15 246.51,-775.12 249.88,-766.68"/>
<polygon points="253.09,-768.09 253.55,-757.51 246.59,-765.49 253.09,-768.09"/>
</g>
<g class="m-node m-flat">
<title>[A14] fprop_u4:A</title>
<ellipse cx="114.96" cy="-882" rx="52.96" ry="18"/>
<text text-anchor="middle" x="114.96" y="-878.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A14] fprop_u4:A</text>
</g>
<g class="m-edge">
<title>[A14] fprop_u4:A&#45;&gt;[A15] fprop_u4:Y</title>
<path d="M135.97,-865.12C151.97,-854.93 174.28,-841.62 193.52,-830.75"/>
<polygon points="195.19,-833.82 202.22,-825.9 191.78,-827.71 195.19,-833.82"/>
</g>
<g class="m-edge">
<title>[A14] fprop_u4:A&#45;&gt;[A15] fprop_u4:Y</title>
<path d="M144.69,-866.67C162.46,-856.88 184.87,-843.73 202.72,-832.67"/>
<polygon points="204.22,-835.86 210.83,-827.58 200.5,-829.94 204.22,-835.86"/>
</g>
<g class="m-node m-flat">
<title>[A13] fprop_u1:Y</title>
<ellipse cx="114.96" cy="-954" rx="52.96" ry="18"/>
<text text-anchor="middle" x="114.96" y="-950.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A13] fprop_u1:Y</text>
</g>
<g class="m-edge">
<title>[A13] fprop_u1:Y&#45;&gt;[A14] fprop_u4:A</title>
<path d="M114.96,-935.7C114.96,-928.41 114.96,-919.73 114.96,-911.54"/>
<polygon points="118.46,-911.62 114.96,-901.62 111.46,-911.62 118.46,-911.62"/>
</g>
<g class="m-node m-flat">
<title>[A12] fprop_u1:A</title>
<ellipse cx="52.96" cy="-1026" rx="52.96" ry="18"/>
<text text-anchor="middle" x="52.96" y="-1022.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A12] fprop_u1:A</text>
</g>
<g class="m-edge">
<title>[A12] fprop_u1:A&#45;&gt;[A13] fprop_u1:Y</title>
<path d="M62.09,-1008.05C68.92,-999.29 78.34,-988.45 87.39,-978.86"/>
<polygon points="89.67,-981.53 94.13,-971.92 84.65,-976.65 89.67,-981.53"/>
</g>
<g class="m-edge">
<title>[A12] fprop_u1:A&#45;&gt;[A13] fprop_u1:Y</title>
<path d="M72.79,-1009.12C81.23,-1000.68 90.85,-990.1 98.86,-980.55"/>
<polygon points="101.42,-982.95 104.99,-972.97 95.98,-978.54 101.42,-982.95"/>
</g>
<g class="m-node m-flat">
<title>[A11] fprop_inp1</title>
<ellipse cx="52.96" cy="-1098" rx="51.63" ry="18"/>
<text text-anchor="middle" x="52.96" y="-1094.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A11] fprop_inp1</text>
</g>
<g class="m-edge">
<title>[A11] fprop_inp1&#45;&gt;[A12] fprop_u1:A</title>
<path d="M52.96,-1079.7C52.96,-1072.41 52.96,-1063.73 52.96,-1055.54"/>
<polygon points="56.46,-1055.62 52.96,-1045.62 49.46,-1055.62 56.46,-1055.62"/>
</g>
<g class="m-node m-flat">
<title>[A10] fprop_u1:B</title>
<ellipse cx="176.96" cy="-1026" rx="52.96" ry="18"/>
<text text-anchor="middle" x="176.96" y="-1022.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A10] fprop_u1:B</text>
</g>
<g class="m-edge">
<title>[A10] fprop_u1:B&#45;&gt;[A13] fprop_u1:Y</title>
<path d="M157.13,-1009.12C148.68,-1000.68 139.06,-990.1 131.06,-980.55"/>
<polygon points="133.94,-978.54 124.92,-972.97 128.5,-982.95 133.94,-978.54"/>
</g>
<g class="m-edge">
<title>[A10] fprop_u1:B&#45;&gt;[A13] fprop_u1:Y</title>
<path d="M167.83,-1008.05C161,-999.29 151.58,-988.45 142.52,-978.86"/>
<polygon points="145.26,-976.65 135.79,-971.92 140.24,-981.53 145.26,-976.65"/>
</g>
<g class="m-node m-flat">
<title>[A9] fprop_inp2</title>
<ellipse cx="176.96" cy="-1098" rx="48.52" ry="18"/>
<text text-anchor="middle" x="176.96" y="-1094.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A9] fprop_inp2</text>
</g>
<g class="m-edge">
<title>[A9] fprop_inp2&#45;&gt;[A10] fprop_u1:B</title>
<path d="M176.96,-1079.7C176.96,-1072.41 176.96,-1063.73 176.96,-1055.54"/>
<polygon points="180.46,-1055.62 176.96,-1045.62 173.46,-1055.62 180.46,-1055.62"/>
</g>
<g class="m-node m-flat">
<title>[A8] fprop_out</title>
<ellipse cx="438.96" cy="-594" rx="45.86" ry="18"/>
<text text-anchor="middle" x="438.96" y="-590.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A8] fprop_out</text>
</g>
<g class="m-edge">
<title>[A8] fprop_out&#45;&gt;[A25] bprop_out</title>
<path d="M440.19,-575.7C440.71,-568.41 441.33,-559.73 441.92,-551.54"/>
<polygon points="445.41,-551.84 442.63,-541.61 438.42,-551.34 445.41,-551.84"/>
</g>
<g class="m-node m-flat">
<title>[A7] fprop_u3:Y</title>
<ellipse cx="434.96" cy="-666" rx="49.85" ry="18"/>
<text text-anchor="middle" x="434.96" y="-662.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A7] fprop_u3:Y</text>
</g>
<g class="m-edge">
<title>[A7] fprop_u3:Y&#45;&gt;[A8] fprop_out</title>
<path d="M435.95,-647.7C436.36,-640.41 436.86,-631.73 437.33,-623.54"/>
<polygon points="440.82,-623.8 437.89,-613.62 433.83,-623.4 440.82,-623.8"/>
</g>
<g class="m-node m-flat">
<title>[A6] fprop_u3:A</title>
<ellipse cx="434.96" cy="-738" rx="49.85" ry="18"/>
<text text-anchor="middle" x="434.96" y="-734.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A6] fprop_u3:A</text>
</g>
<g class="m-edge">
<title>[A6] fprop_u3:A&#45;&gt;[A7] fprop_u3:Y</title>
<path d="M429.04,-719.7C428.29,-712.41 428.05,-703.73 428.31,-695.54"/>
<polygon points="431.8,-695.82 428.96,-685.61 424.81,-695.36 431.8,-695.82"/>
</g>
<g class="m-edge">
<title>[A6] fprop_u3:A&#45;&gt;[A7] fprop_u3:Y</title>
<path d="M440.87,-719.7C441.62,-712.41 441.87,-703.73 441.6,-695.54"/>
<polygon points="445.1,-695.36 440.95,-685.61 438.11,-695.82 445.1,-695.36"/>
</g>
<g class="m-node m-flat">
<title>[A5] fprop_u2:Y</title>
<ellipse cx="426.96" cy="-810" rx="49.85" ry="18"/>
<text text-anchor="middle" x="426.96" y="-806.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A5] fprop_u2:Y</text>
</g>
<g class="m-edge">
<title>[A5] fprop_u2:Y&#45;&gt;[A6] fprop_u3:A</title>
<path d="M428.93,-791.7C429.77,-784.41 430.76,-775.73 431.7,-767.54"/>
<polygon points="435.17,-767.94 432.83,-757.61 428.22,-767.15 435.17,-767.94"/>
</g>
<g class="m-node m-flat">
<title>[A4] fprop_u2:A</title>
<ellipse cx="426.96" cy="-882" rx="49.85" ry="18"/>
<text text-anchor="middle" x="426.96" y="-878.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A4] fprop_u2:A</text>
</g>
<g class="m-edge">
<title>[A4] fprop_u2:A&#45;&gt;[A5] fprop_u2:Y</title>
<path d="M421.04,-863.7C420.29,-856.41 420.05,-847.73 420.31,-839.54"/>
<polygon points="423.8,-839.82 420.96,-829.61 416.81,-839.36 423.8,-839.82"/>
</g>
<g class="m-edge">
<title>[A4] fprop_u2:A&#45;&gt;[A5] fprop_u2:Y</title>
<path d="M432.87,-863.7C433.62,-856.41 433.87,-847.73 433.6,-839.54"/>
<polygon points="437.1,-839.36 432.95,-829.61 430.11,-839.82 437.1,-839.36"/>
</g>
<g class="m-node m-flat">
<title>[A3] fprop_u4:B</title>
<ellipse cx="235.96" cy="-882" rx="49.85" ry="18"/>
<text text-anchor="middle" x="235.96" y="-878.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A3] fprop_u4:B</text>
</g>
<g class="m-edge">
<title>[A3] fprop_u4:B&#45;&gt;[A15] fprop_u4:Y</title>
<path d="M229.3,-863.7C228.24,-856.41 227.62,-847.73 227.53,-839.54"/>
<polygon points="231.03,-839.69 227.76,-829.62 224.03,-839.53 231.03,-839.69"/>
</g>
<g class="m-edge">
<title>[A3] fprop_u4:B&#45;&gt;[A15] fprop_u4:Y</title>
<path d="M241.13,-863.7C241.57,-856.41 241.44,-847.73 240.83,-839.54"/>
<polygon points="244.31,-839.17 239.75,-829.61 237.35,-839.93 244.31,-839.17"/>
</g>
<g class="m-node m-flat">
<title>[A2] fprop_f1:Q</title>
<ellipse cx="408.96" cy="-954" rx="48.96" ry="18"/>
<text text-anchor="middle" x="408.96" y="-950.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A2] fprop_f1:Q</text>
</g>
<g class="m-edge">
<title>[A2] fprop_f1:Q&#45;&gt;[A4] fprop_u2:A</title>
<path d="M413.41,-935.7C415.3,-928.32 417.56,-919.52 419.69,-911.25"/>
<polygon points="423.08,-912.13 422.18,-901.57 416.3,-910.38 423.08,-912.13"/>
</g>
<g class="m-edge">
<title>[A2] fprop_f1:Q&#45;&gt;[A3] fprop_u4:B</title>
<path d="M376.82,-940C349.11,-928.79 308.89,-912.51 278.51,-900.22"/>
<polygon points="280.2,-897.13 269.62,-896.62 277.57,-903.61 280.2,-897.13"/>
</g>
<g class="m-node m-flat">
<title>[A1] fprop_f1:CLK</title>
<ellipse cx="365.96" cy="-1026" rx="56.06" ry="18"/>
<text text-anchor="middle" x="365.96" y="-1022.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A1] fprop_f1:CLK</text>
</g>
<g class="m-edge">
<title>[A1] fprop_f1:CLK&#45;&gt;[A16] fprop_f1:D</title>
<path d="M357.05,-1007.81C337.48,-957.4 295.32,-812.25 285.96,-792 281.83,-783.07 276.4,-773.87 271.49,-765.69"/>
<polygon points="274.59,-764.06 266.45,-757.27 268.58,-767.65 274.59,-764.06"/>
</g>
<g class="m-edge">
<title>[A1] fprop_f1:CLK&#45;&gt;[A16] fprop_f1:D</title>
<path d="M364.98,-1007.81C355.48,-957.4 313.32,-812.25 303.96,-792 299.56,-782.48 293.68,-772.66 287.58,-764.09"/>
<polygon points="290.44,-762.06 281.58,-756.24 284.87,-766.31 290.44,-762.06"/>
</g>
<g class="m-edge">
<title>[A1] fprop_f1:CLK&#45;&gt;[A2] fprop_f1:Q</title>
<path d="M370.67,-1007.7C374.86,-999.49 380.79,-989.52 386.79,-980.48"/>
<polygon points="389.57,-982.6 392.39,-972.39 383.82,-978.62 389.57,-982.6"/>
</g>
<g class="m-edge">
<title>[A1] fprop_f1:CLK&#45;&gt;[A2] fprop_f1:Q</title>
<path d="M381.99,-1008.41C387.71,-1000.51 393.89,-990.85 399,-981.94"/>
<polygon points="402,-983.74 403.7,-973.29 395.85,-980.4 402,-983.74"/>
</g>
<g class="m-node m-flat">
<title>[A0] fprop_tau2015_clk</title>
<ellipse cx="365.96" cy="-1098" rx="68.93" ry="18"/>
<text text-anchor="middle" x="365.96" y="-1094.12" font-family="Helvetica,sans-Serif" font-size="10.00">[A0] fprop_tau2015_clk</text>
</g>
<g class="m-edge">
<title>[A0] fprop_tau2015_clk&#45;&gt;[A1] fprop_f1:CLK</title>
<path d="M365.96,-1079.7C365.96,-1072.41 365.96,-1063.73 365.96,-1055.54"/>
<polygon points="369.46,-1055.62 365.96,-1045.62 362.46,-1055.62 369.46,-1055.62"/>
</g>
</g>
</svg>
</div></section><section id="UseCaseOpenTimerPerformanceImprovement"><h2><a href="#UseCaseOpenTimerPerformanceImprovement">Performance Improvement</a></h2><p>We compare the performance between OpenTimer v1 and v2. We evaluated the runtime versus incremental iterations under 16 CPUs on two industrial circuit designs tv80 (5.3K gates and 5.3K nets) and vga_lcd (139.5K gates and 139.6K nets) with 45nm NanGate cell libraris. Each incremental iteration refers a design modification followed by a timing query to trigger a timing update. In v1, this includes the time to reconstruct the data structure required by OpenMP to alter the task dependencies. In v2, this includes the time to create and launch a new task dependency graph</p><img class="m-image" src="opentimer_2.png" alt="Image" /><p>The scalability of Taskflow is shown in the Figure below. We used two million-scale designs, netcard (1.4M gates) and leon3mp (1.2M gates) to evaluate the runtime of v1 and v2 across different number of CPUs. There are two important observations. First, v2 is slightly slower than v1 at one CPU (3-4%), where all OpenMP&#x27;s constructs are literally disabled. This shows the graph overhead of Taskflow; yet it is negligible. Second, v2 is consistently faster than v1 regardless of CPU numbers except one. This highlights that Taskflow&#x27;s programming model largely improves the design of a parallel VLSI timing engine that would otherwise not be possible with OpenMP.</p><img class="m-image" src="opentimer_3.png" alt="Image" /></section><section id="UseCaseOpenTimerConclusion"><h2><a href="#UseCaseOpenTimerConclusion">Conclusion</a></h2><p>Programming models matter. Different models give different implementations. The parallel code sections may run fast, yet the data structures to support a parallel decomposition strategy may outweigh its parallelism benefits. In OpenTimer v1, loop-based OpenMP code is very fast. But it&#x27;s too costly to maintain the pipeline data structure over iterations.</p></section><section id="UseCaseOpenTimerReferences"><h2><a href="#UseCaseOpenTimerReferences">References</a></h2><ul><li>Tsung-Wei Huang, Guannan Guo, Chun-Xun Lin, and Martin Wong, &quot;<a href="https://tsung-wei-huang.github.io/papers/tcad21-ot2.pdf">OpenTimer v2: A New Parallel Incremental Timing Analysis Engine</a>,&quot; <em>IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)</em>, vol. 40, no. 4, pp. 776-786, April 2021</li><li>Tsung-Wei Huang, Chun-Xun Lin, Guannan Guo, and Martin Wong, &quot;<a href="ipdps19.pdf">Cpp-Taskflow: Fast Task-based Parallel Programming using Modern C++</a>,&quot; <em>IEEE International Parallel and Distributed Processing Symposium (IPDPS)</em>, pp. 974-983, Rio de Janeiro, Brazil, 2019.</li><li>Tsung-Wei Huang and Martin Wong, &quot;<a href="huang_15_01.pdf">OpenTimer: A High-Performance Timing Analysis Tool</a>,&quot; <em>IEEE/ACM International Conference on Computer-Aided Design (ICCAD)</em>, pp. 895-902, Austin, TX, 2015.</li></ul></section>
      </div>
    </div>
  </div>
</article></main>
<div class="m-doc-search" id="search">
  <a href="#!" onclick="return hideSearch()"></a>
  <div class="m-container">
    <div class="m-row">
      <div class="m-col-m-8 m-push-m-2">
        <div class="m-doc-search-header m-text m-small">
          <div><span class="m-label m-default">Tab</span> / <span class="m-label m-default">T</span> to search, <span class="m-label m-default">Esc</span> to close</div>
          <div id="search-symbolcount">&hellip;</div>
        </div>
        <div class="m-doc-search-content">
          <form>
            <input type="search" name="q" id="search-input" placeholder="Loading &hellip;" disabled="disabled" autofocus="autofocus" autocomplete="off" spellcheck="false" />
          </form>
          <noscript class="m-text m-danger m-text-center">Unlike everything else in the docs, the search functionality <em>requires</em> JavaScript.</noscript>
          <div id="search-help" class="m-text m-dim m-text-center">
            <p class="m-noindent">Search for symbols, directories, files, pages or
            modules. You can omit any prefix from the symbol or file path; adding a
            <code>:</code> or <code>/</code> suffix lists all members of given symbol or
            directory.</p>
            <p class="m-noindent">Use <span class="m-label m-dim">&darr;</span>
            / <span class="m-label m-dim">&uarr;</span> to navigate through the list,
            <span class="m-label m-dim">Enter</span> to go.
            <span class="m-label m-dim">Tab</span> autocompletes common prefix, you can
            copy a link to the result using <span class="m-label m-dim">⌘</span>
            <span class="m-label m-dim">L</span> while <span class="m-label m-dim">⌘</span>
            <span class="m-label m-dim">M</span> produces a Markdown link.</p>
          </div>
          <div id="search-notfound" class="m-text m-warning m-text-center">Sorry, nothing was found.</div>
          <ul id="search-results"></ul>
        </div>
      </div>
    </div>
  </div>
</div>
<script src="search-v2.js"></script>
<script src="searchdata-v2.js" async="async"></script>
<footer><nav>
  <div class="m-container">
    <div class="m-row">
      <div class="m-col-l-10 m-push-l-1">
        <p>Taskflow handbook is part of the <a href="https://taskflow.github.io">Taskflow project</a>, copyright © <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>, 2018&ndash;2024.<br />Generated by <a href="https://doxygen.org/">Doxygen</a> 1.9.6 and <a href="https://mcss.mosra.cz/">m.css</a>.</p>
      </div>
    </div>
  </div>
</nav></footer>
</body>
</html>
